package zuochengyun;

import Tree.TreeNode;

public class PostArrayToBst {

	public TreeNode postArrayToBST(int[] posArr, int start, int end){
		if(start > end){
			return null;
		}
		return postToBST(posArr, 0, posArr.length - 1);
	}
	
	public TreeNode postToBST(int[] posArray, int start, int end){
		if(start > end){
			return null;
		}
		TreeNode head = new TreeNode(posArray[end]);
		int less = -1;
		int more = end;
		for (int i = start; i < end; i++) {
			//寻找小于根节点的分界线less的值
			if(posArray[end] > posArray[i]){
				less = i;
			}else{
				//初始more是等于end的
				//之后不等于end，所以more的值不会变
				//为什么不找到之后直接break呢
				more = more == end ? i : more;
			}
		}
		head.left = postToBST(posArray, start, less);
		head.left = postToBST(posArray, more, end);
		return head;
	}
	
}
